package br.uece.paa.sa.jssp.alg;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.math.BigDecimal;
import java.util.Random;

import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JProgressBar;
import javax.swing.JTextField;

import org.jfree.chart.ChartFactory;
import org.jfree.chart.ChartFrame;
import org.jfree.chart.JFreeChart;
import org.jfree.chart.axis.NumberAxis;
import org.jfree.chart.plot.PlotOrientation;
import org.jfree.data.xy.XYSeries;
import org.jfree.data.xy.XYSeriesCollection;

import br.uece.paa.sa.jssp.ui.JsspMain;

/**
 * 
 * @author Mario Alves de Moraes Neto
 * @author Tales Paiva Nogueira
 */
public class JsspSa extends Thread {
	BufferedReader br;
	static short n, m;
	short[][] tempo, ordem;
	int[][] result;
	Integer otimo;
	short[] s, sInicial; // configuracao final
//	PrintWriter log;
	int nsucc, seq;
	XYSeries series1 = new XYSeries("Makespan"); //grafico
	Random r = new Random();
	private short[] res;
	private boolean mostrarGrafico;
	int L, M, P;
	double alfa = 0.9;
	JsspMain ui;
	private long tempoGasto;
	JProgressBar prog;
	short[] confSequencial;  // utilizada p/ gerar a configuracao inicial
        private double tempInicial;
        private double temperatura;

	public JsspSa(File file, boolean mostraGraf, int maxSuc, int maxIter, int maxPert, double a, JsspMain ui) {
		try {
			mostrarGrafico = mostraGraf;
			L = maxSuc;
			M = maxIter;
			P = maxPert;
			alfa = a;
			this.ui = ui;
			prog = ui.getProgressBar();
			prog.setIndeterminate(true);

			this.ui.getTxtMelhorSolucao().setText("");
			this.ui.getTxtSolucaoInicial().setText("");
			this.ui.getTimeElapsedLabel().setText("Tempo gasto: ");
                        this.ui.getLblTempIni().setText("Temperatura inicial: ");
                        this.ui.getLblTempFim().setText("Temperatura final: ");
                        
			
			
//			System.err.println("L="+L+" M="+M+" P="+P+" alfa="+alfa);
//			log = new PrintWriter(new BufferedWriter(new FileWriter("log "+System.currentTimeMillis()+".txt")));

			/* leitura dos dados da instancia */
			br = new BufferedReader(new FileReader(file));

			String line = new String();

			line = br.readLine();
			String[] temp = line.split(" +");

			n = Short.parseShort(temp[0]); // numero de jobs/tarefas
			m = Short.parseShort(temp[1]); // numero de maquinas

			// System.out.println("==> n=" + n + " m=" + m);

			tempo = new short[n][m]; // tempo de processamento das tarefas
			ordem = new short[n][m]; // ordem de processamento das tarefas
			confSequencial = new short[n];
			
			short i = 0, j = 0;
			while (line != null) {

				// System.out.println(line);
				line = line.trim();
				temp = line.split(" +");
				if (temp.length <= 2) { // conteudo da primeira linha
					line = br.readLine();
					continue;
				}

//				for (short k = 1; k <= temp.length; k += 2) {
				for (short k = 0; k < temp.length; k ++) {
					ordem[i][j] = Short.parseShort(temp[k]);
					k++;
					tempo[i][j] = Short.parseShort(temp[k]);
					// System.out.println(temp[k]
					// + " adicionado na coluna (maquina) " + j
					// + ", linha (tarefa) " + i);
					j++;
				}
				confSequencial[i] = i;
				i++;
				j = 0;
				line = br.readLine();
				
			}
//			System.out.println("confSequencial "+printArray(confSequencial));
//			 System.out.println("matrizes criadas");

			/* fim da leitura dos dados da instancia */
			//
//			short [] teste = 	
//								teste4
//								{0,1,2,3};
//								{0,1,3,2};
//								{0,2,1,3};
//								{0,2,3,1};
			
//								{1, 5, 3, 6, 4, 2, 0, 9, 8, 7}; // car5

//								teste3			
//								{0,1,2}; //ok
//								{0,2,1}; //ok
////							{1,0,2}; //ok
////							{1,2,0}; //ok
////							{2,0,1}; //ok
//								{2,1,0}; //ok
//			System.out.println(funcaoObjetivo(teste));
//			System.out.println(funcaoObjetivo2(teste));
//			System.out.println(funcaoObjetivo3(teste));
//			short [][] testes = {{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
//			for (int k = 0; k < testes.length; k++) {
//				System.out.println(printArray(testes[k])+" makespan = "+funcaoObjetivo2(testes[k]));	
//			}
//			
//			System.exit(0);
			//

		} catch (FileNotFoundException fnf) {
			JOptionPane.showMessageDialog(null,
					"Verifique se o arquivo selecionado existe.\n"
							+ fnf.getMessage(), "Arquivo nao encontrado",
					JOptionPane.ERROR_MESSAGE);
                        
		} catch (NumberFormatException nfe) {
			JOptionPane.showMessageDialog(null,
					"Verifique se o arquivo estï¿½ no formato correto.\n"
							+ nfe.getMessage(), "Erro de leitura",
					JOptionPane.ERROR_MESSAGE);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private void mostraGrafico() {
		XYSeriesCollection dataset = new XYSeriesCollection();
		dataset.addSeries(series1);

		JFreeChart chart = ChartFactory.createXYLineChart(null,
				"Numero de iteracoes", "Makespan", dataset,
				PlotOrientation.VERTICAL, false, true, false);

		NumberAxis numberAxis = (NumberAxis) chart.getXYPlot()
				.getRangeAxis();
		numberAxis.setAutoRangeIncludesZero(false);
		numberAxis.setAutoRange(true);
		
                // marcar pontos
		//XYLineAndShapeRenderer renderer = (XYLineAndShapeRenderer) chart.getXYPlot().getRenderer();
		//renderer.setShapesVisible(true);
		//renderer.setShapesFilled(true);

		ChartFrame frame = new ChartFrame("Evolucao", chart);
		frame.pack();
		frame.setVisible(true);
		
	}

	private void aceita(short[] configuracao2, int f) {
//		log.println(" OK ");
		s = configuracao2.clone();
		nsucc++;
//		series1.add(seq, f);	seq++;
		
	}

	/**
	 * Metodo qye calcula a temperatua inicial
	 * @param conf uma configuracao inicial qualquer
	 * @param nTent numero de tentativas
	 * @return a temperatura inicial
	 */
	private double calcTempInicial(short[] conf, int nTent, Random r) {
		
		int prevObj = 0; // valor da funcao objetivo anterior
		int k = 0; // numero de tentativas em que o valor foi maior
		int soma = 0; // soma dos k valores
		int obj = 0; // valor da funcao objetivo
		

		/* inicio do calculo da temperatura inicial */
		while (nTent > 0) {
			// log.print(">> " + (101 - nTent) + " << ");

			obj = funcaoObjetivo3(conf);

			// Verificacao se o otimo foi encontrado
			// otimo = null = primeira execucao
			if (otimo == null || obj < otimo.intValue()) {
				otimo = obj; // eh a melhor configuracao no momento
				s = conf.clone();
			}

			if (obj > prevObj) { // o valor atual eh maior q o anterior
				k++;
				soma += obj;
			}

			prevObj = obj; // o atual passa a ser o anterior
			conf = perturba(conf, r); // troca 2 elementos
			nTent--;
		}

		int media;
		if (k > 0) // evita divisao por zero
			media = soma / k; // temperatura inicial
		else
			media = 1000; // TODO melhorar valor default
		
		return 4.48 * media;

	}

	/**
	 * Realiza uma perturbacao na configuracao passada como parametro atraves da
	 * troca de dois elementos aleatoriamente escolhidos
	 * 
	 * @param c
	 *            o array a ser modificado
	 * @return o mesmo array, com dois elementos trocados
	 */
	private short[] perturba(short[] src, Random r) {
//		short[] res = new short[src.length];

//		System.arraycopy(src, 0, res, 0, src.length);
		if (res == null)
			res = new short[src.length];
		
		res = src.clone();
		
		int index1 = r.nextInt(res.length);
		int index2 = r.nextInt(res.length);
		if (index1 != index2){
			short aux = res[index1];
			res[index1] = res[index2];
			res[index2] = aux;
		}

		return res;
	}

	/**
	 * Metodo que calcula a funcao objetivo para o JSSP, que e' o tempo
	 * em que o ultimo job termina na ultima maquina
	 * 
	 * @param sequencia
	 *            a sequencia dos jobs
	 * @return o tempo de execucao do ultimo job
	 */
	private int funcaoObjetivo(short[] sequencia) { 
		result = new int[n][m];
		for (int i = 0; i < n; i++) {
			short k = sequencia[i];
			// log.print(k + ": ");

			for (int j = 0; j < m; j++) {
				// log.print(" " + matriz[k][j]);

				if (i == 0 && j == 0) { // primeira linha e primeira coluna
					result[i][j] = tempo[k][j];
				} else if (j == 0 && i > 0) { // primeira coluna
					result[i][j] = tempo[k][j] + result[i - 1][j];
				} else if (i == 0 && j > 0) { // primeira linha
					result[i][j] = tempo[k][j] + result[i][j - 1];
				} else {
					if (result[i - 1][j] >= result[i][j - 1])
						result[i][j] = tempo[k][j] + result[i - 1][j];
					else
						result[i][j] = tempo[k][j] + result[i][j - 1];
				}

			}

		}

		return result[n - 1][m - 1];
	}
	
	/**
	 * Metodo que calcula a funcao objetivo para o JSSP, que e' o tempo
	 * em que o ultimo job termina na ultima maquina
	 * 
	 * @param sequencia
	 *            a sequencia dos jobs
	 * @return o tempo de execucao do ultimo job
	 */
	private int funcaoObjetivo2(short[] sequencia) {
		result = new int[n][m];
		int [][] inicio = new int[n][m]; // guarda o tempo de que cada tarefa eh iniciada
		short o; // ordem
		
//		Integer [] fim = new Integer[m]; // guarda os tempos finais na maquina o, da tarefa i
//		Integer [] ini = new Integer[m]; // guarda os tempos iniciais na maquina o, da tarefa i
		//Integer [] gap = new Integer[m];
		int ind = 0;
		int oAnt = 0; // o anterior
		
		for (int i = 0; i < sequencia.length; i++) {
			short k = sequencia[i];
//			boolean zero = false;
			for (int j = 0; j < m; j++) {
				o = ordem[k][j];
				
				if (i == 0 && j == 0) { // primeira linha e primeira insercao
					result[i][o] = tempo[k][o];
					inicio[i][o] = result[i][o] - tempo[k][o];
				} else if (i == 0 && j > 0) { // primeira linha, exceto primeira insercao
					result[i][o] = tempo[k][o] + result[i][ordem[k][j-1]];
					inicio[i][o] = result[i][o] - tempo[k][o];
				} else if (j==0) { // primera insercao das outras linhas (i>0)
					for (ind = i-1; ind >= 0; ind--) {
						if ( !hasZero(inicio, o, i) && tempo[k][o] <= inicio[ind][o]) {
							result[i][o] = tempo[k][o];
							inicio[i][o] = 0;
						} else if (result[i][o] < result[ind][o] + tempo[k][o]) {
							result[i][o] = result[ind][o] + tempo[k][o];
							inicio[i][o] = result[ind][o];
						} 
					}
				} else {
					oAnt = ordem[k][j-1];
					for (ind = i-1; ind >= 0; ind--) {
						
						if (result[i][oAnt] > result[ind][o]){
							result[i][o] = result[i][oAnt] + tempo[k][o];
							inicio[i][o] = result[i][oAnt];
						} else if (result[i][oAnt]+tempo[k][o] < inicio[ind][o]){
							result[i][o] = result[i][oAnt] + tempo[k][o];
							inicio[i][o] = result[i][oAnt];
						} else if (ind >= 1 && 
								inicio[ind][o] > result[ind-1][o] && 
								inicio[ind][o] - result[ind-1][o] >= tempo[k][o] &&
								result[ind-1][o] > result[i][oAnt] ){
								
							result[i][o] = result[ind-1][o] + tempo[k][o];
							inicio[i][o] = result[i][o] - tempo[k][o];
						} 
						else if (result[i][o] < result[ind][o] + tempo[k][o]){
							result[i][o] = result[ind][o] + tempo[k][o];
							inicio[i][o] = result[ind][o];
							break;
						}
						
					}
					
				}
				
			}
			
		}
//		System.out.println();
		int makespan = Integer.MIN_VALUE;
		for (int p = 0; p < n; p++) {
			for (int q = 0; q < m; q++) {
				if (result[p][q] > makespan)
					makespan = result[p][q]; 
			}
		}
		if (makespan == Integer.MIN_VALUE) // algo deve ter dado errado :(
			System.err.println("makespan == Integer.MIN_VALUE!");
			
		return makespan;

	}
	
	/**
	 * Metodo que informa se uma dada coluna em uma matriz possui
	 * o valor zero em alguma posicao
	 * @param matriz matriz onde o zero sera buscado 
	 * @param index o indice da coluna onde o zero sera buscado
	 * @param currI o indice de limite de linha de busca
	 * @return true se a coluna <index> na matriz <matriz> tem
	 * 			zero em alguma posicao limitada por <currI>, 
	 * 			false, caso contrario 
	 */
	private boolean hasZero(int[][] matriz, int index, int currI) {
		Integer [] res = new Integer [matriz.length];
		for (int i = 0; i < currI; i++) 
			for (int j = 0; j < matriz.length; j++) 
				if (index == j)
					res[i] = matriz[i][j]; 
		
		for (int i = 0; i < res.length; i++) 
			if (res[i]!=null && res[i] == 0)
				return true;
		
		return false;
	}
	
	//
    @SuppressWarnings("static-access")
	public int funcaoObjetivo3(short[] sequencia){
        
        
        short[][] mTempoSeq = new short[this.n][this.m];
        short[][] mOrdemSeq = new short[this.n][this.m];
        
        //organizar na sequencia
        for(int i = 0; i < this.n; i++){
            mTempoSeq[i] = tempo[sequencia[i]];
            mOrdemSeq[i] = ordem[sequencia[i]];
        }
        
        int[] ultimaMaq = new int[this.m];
        int[] ultimoJob = new int[this.n];
        
        int maqAtual;
        int tempoOpAtual;
        
        for(int opAtual = 0; opAtual < this.m; opAtual++)
            for(int jobAtual = 0; jobAtual < this.n; jobAtual++){
                maqAtual = mOrdemSeq[jobAtual][opAtual];
                tempoOpAtual = mTempoSeq[jobAtual][maqAtual];
                
                if(ultimoJob[jobAtual] <= ultimaMaq[maqAtual]){
                    ultimaMaq[maqAtual] += tempoOpAtual;
                    ultimoJob[jobAtual] = ultimaMaq[maqAtual];
                }else{
                    ultimoJob[jobAtual] += tempoOpAtual;
                    ultimaMaq[maqAtual] = ultimoJob[jobAtual];
                }
            }
        
        //agora procurar o tempo em que a ultima maquina parou
        int tempo = 0;
        for(int m = 0; m < this.m; m++)
            if(tempo < ultimaMaq[m])
                tempo = ultimaMaq[m];
        
        //retorna o tempo de parada da ultima maquina
        return tempo;
    }
	
	/**
	 * Gera uma configuracao inicial consistindo em um array com o tamanho do
	 * numero de tarefas que representa uma dada sequencia de tarefas. Nenhum
	 * elemento do array eh repetido.
	 * 
	 * @param n
	 *            o tamanho do array a ser gerado
	 * @return um array de tamanho n com uma sequencia aleatoria de numeros
	 */
	private short[] geraConfInicial(int n, short[] array) {
		int swap;
		short aux;
		Random random = new Random();
//		short[] array = new short[n];

		// insere os elementos no array
		// TODO criar esse array ao ler os dados da intancia -> O(n) 
//		for (short i = 0; i < array.length; i++) {
//			array[i] = i;
//		}

		// embaralha o array
		for (int pos = n - 1; pos > 0; --pos) {
			// Obtem uma posicao aleatoria para trocar. pos + 1 eh usado para
			// que a faixa do numero aleatorio inclua a posicao atual.
			swap = random.nextInt(pos + 1);

			// troca os elementos.
			aux = array[pos];
			array[pos] = array[swap];
			array[swap] = aux;
		}

//		log.println("Configuracao inicial =  " + printArray(array));

		return array;
	}

	public String printArray(short[] a) {
		StringBuffer s = new StringBuffer();
		for (int i = 0; i < a.length; i++) {
			s.append(a[i] + " ");
		}
		return s.toString();
	}

	@Override
	public void run() {
		short[] configuracao2;
		sInicial = geraConfInicial(n, confSequencial); // configuracao inicial
		//res = new short[configuracao1.length];
		temperatura = calcTempInicial(sInicial, 100, r);
		tempInicial = temperatura;

		/* inicio das iteracoes do SA */
		
		int f1, f2;
		BigDecimal delta, expo, t;
		
		double metropolis=0, rand=0;

		int j = 1, i = 0;
		
		tempoGasto = System.currentTimeMillis();
                
		do {
			i = 1;
			nsucc = 0;
			//atualiza barra de progresso
//			prog.setValue((int) (100 - ((temperatura*100)/temperaturaInicial)));
			//
			do {
				if (Thread.interrupted()) {
			        // Botao PARAR foi pressionado
					mostrarResultado();
                                    return;
                                }

//				log.println("***************************");
				
				f1 = funcaoObjetivo3(s);
//				log.println(printArray(s)+" = "+f1);
				
				configuracao2 = perturba(s, r);

				f2 = funcaoObjetivo3(configuracao2);
//				log.println(printArray(configuracao2)+" = "+f2);
				
				delta = new BigDecimal(f2 - f1);
				
//				log.print(" t= "+temperatura);
//				log.print(" delta= "+delta.doubleValue());
				
				if (delta.doubleValue() < 0){
					
					aceita(configuracao2, f2);
					
				} else if (delta.doubleValue() > 0) {
					
					// Criterio de Metropolis
					t = new BigDecimal(temperatura);
					
					expo = delta.negate().divide(t, 16, BigDecimal.ROUND_DOWN);
					metropolis = Math.exp(expo.doubleValue());
					rand = r.nextDouble();
					
					if ( metropolis > rand) 
						aceita(configuracao2, f2);
					
//					log.print(" expo= "+expo.doubleValue());
//					log.print(" metr= "+metropolis);
//					log.print(" rand= "+rand);
					
				}
				
//				log.println();
				i++;

			} while (nsucc < L && i < P); // equilibrio //&&
			temperatura =  temperatura * alfa;
			series1.add(j, f1);
			j++;
//			series1.add(seq, f1);	//seq++;
			//System.err.println("j "+j);
		} while (/*nsucc == 0 ||*/ j < M); // condicao de parada
		
		tempoGasto = System.currentTimeMillis() - tempoGasto;
//		System.out.println("temp final: "+temperatura);
//		log.println("solucao otima: "+printArray(s)+" = "+funcaoObjetivo(s));
//		log.println("tempo decorrido: "+(tempo/100)+"s");
//		
//		log.flush();
//		log.close();

		mostrarResultado();
		
	}
	
	private void mostrarResultado() {
		
		//atualizar Resultado no form
		//s tempo
		JTextField melhor = ui.getTxtMelhorSolucao();
		JTextField inicial = ui.getTxtSolucaoInicial();
		JLabel time = ui.getTimeElapsedLabel();
                JLabel ti = ui.getLblTempIni();
                JLabel tf = ui.getLblTempFim();

		inicial.setText(funcaoObjetivo3(sInicial)+" ("+printArray(sInicial)+")");
		melhor.setText(funcaoObjetivo3(s)+" ("+printArray(s)+")");

		time.setText("Tempo gasto: "+(float)tempoGasto/1000+"s");
                ti.setText("Temperatura inicial: "+tempInicial);
                tf.setText("Temperatura final: "+temperatura);
                
		prog.setIndeterminate(false);
//		prog.setValue(100);
		
		if (mostrarGrafico)
			mostraGrafico();
                
        ui.getRunButton().setEnabled(true);
        ui.getStopButton().setEnabled(false);
		
	}

	
}
